% This is LLNCS.DEM the demonstration file of
% the LaTeX macro package from Springer-Verlag
% for Lecture Notes in Computer Science,
% version 2.3 for LaTeX2e
%
\documentclass{llncs}
\usepackage{graphicx}
\usepackage{polyglossia}
\usepackage{amsmath,amsfonts}
\usepackage{xltxtra}
\usepackage{ulem}
\usepackage{hyperref}
\usepackage{tabularx}
\usepackage{ifthen}
\usepackage{wrapfig}
\usepackage{listings}
\usepackage{pseudocode}
\usepackage{algorithm}
\usepackage{algorithmicx}
\floatname{algorithm}{Algorithmus} 
\usepackage{algpseudocode}
\usepackage{subfig}
\usepackage{lscape}
\usepackage{rotating}


\setmainlanguage[spelling=new, latesthyphen=true]{german}
\hypersetup{pdfborder=0 0 0}

%Table-Commands

\usepackage{tikz}
\usetikzlibrary{positioning,shadows,arrows}

\newcounter{columncount}
\newcounter{rowcount}
\newcounter{currentcolumn}
\newcounter{currentrow}

\newcommand{\column}{\value{currentcolumn}}
\newcommand{\row}{\value{currentrow}}

\newcommand{\columns}[1]{\setcounter{columncount}{#1}\addtocounter{columncount}{1}}
\newcommand{\rows}[1]{\setcounter{rowcount}{#1}\addtocounter{rowcount}{1}}
\newcommand{\resetcolumns}{\setcounter{columncount}{0}}
\newcommand{\resetrows}{\setcounter{rowcount}{0}}

\newcommand{\resetcolumn}{\setcounter{currentcolumn}{1}}
\newcommand{\resetrow}{\setcounter{currentrow}{1}}

\newcommand{\inccolumn}{\addtocounter{currentcolumn}{1}}
\newcommand{\incrow}{\addtocounter{currentrow}{1}}

\newcommand{\currentnodecolor}{black}
\newcommand{\nodecolor}[1]{\renewcommand{\currentnodecolor}{#1}}

\newcommand{\currentcellcolor}{white}
\newcommand{\cellcolor}[1]{\renewcommand{\currentcellcolor}{#1}}

\newenvironment{tikztable}{
	\begin{tikzpicture}
	\resetrow
	\resetcolumn
	\resetrows
	\resetcolumns
}{
	\ifthenelse{\row < \value{rowcount}}{
		\foreach \y in {\row,...,\value{rowcount}}{
			\begin{tikzrow}
			\end{tikzrow}
		}
	}{}
	\end{tikzpicture}
}

\newenvironment{tikzrow}{
	\resetcolumn
	\incrow
}{
	\ifthenelse{\column < \value{columncount}}{
		\foreach \x in {\column,...,\value{columncount}}{
			\tikzcell{}
		}{}
	}
}

\newcommand{\tikzcell}[1]{
	\inccolumn
	\fill[color=\currentcellcolor] (\column,-\row) +(-.5,-.5) rectangle ++(.5,.5);
	\draw (\column,-\row) +(-.5,-.5) rectangle ++(.5,.5);
	\draw (\column,-\row) node[color=\currentnodecolor]{#1};
}

\newcommand{\tikznocell}{\inccolumn}

\newcommand{\currentarrowoffset}{0.3}
\newcommand{\arrowoffset}[1]{\renewcommand{\currentarrowoffset}{#1}}

\newcommand{\currentarrowcolor}{red}
\newcommand{\arrowcolor}[1]{\renewcommand{\currentarrowcolor}{#1}}

\newcommand{\currentarrowwidth}{0.2em}
\newcommand{\arrowwidth}[1]{\renewcommand{\currentarrowwidth}{#1}}

\newcommand{\ularrow}{
	\draw [->,color=\currentarrowcolor,line width=\currentarrowwidth] (\column-\currentarrowoffset,-\row+\currentarrowoffset) -- (\column-1+\currentarrowoffset,-\row+1-\currentarrowoffset);
}

\newcommand{\larrow}{
	\draw [->,color=\currentarrowcolor,line width=\currentarrowwidth] (\column-\currentarrowoffset,-\row) -- (\column-1+\currentarrowoffset,-\row);
}

\newcommand{\uarrow}{
	\draw [->,color=\currentarrowcolor,line width=\currentarrowwidth] (\column,-\row+\currentarrowoffset) -- (\column,-\row+1-\currentarrowoffset);
}

\begin{document}

\pagestyle{headings}  % switches on printing of running heads
%
\title{Dynamic Programming mit Anwendung auf Sequence Alignment}
%
\titlerunning{Dynamic Programming}  % abbreviated title (for running head)
%                                     also used for the TOC unless
%                                     \toctitle is used
%
\author{Jean-Bernard Wansi Njengoue (\href{mailto:wansj1@bfh.ch}{\email{wansj1@bfh.ch}}) und Manuel Frischknecht (\href{mailto:frism1@bfh.ch}{\email{frism1@bfh.ch}})}
%
\authorrunning{J-B. Wansi, M. Frischknecht}   % abbreviated author list (for running head)
%
%%%% list of authors for the TOC (use if author list has to be modified)
\tocauthor{Jean-Bernard Wansi, Manuel Frischknecht}
%
\institute{BFH-TI, Quellgasse 21, CH-2501 Biel}

\maketitle              % typeset the title of the contribution

\begin{abstract}
Dynamic Programming ist eine Methode zur Lösung von Problemen in der Optimierung.
Sie basiert auf dem "Aufbrechen" eines Problems in kleinere Teilprobleme und dem Speichern 
und Wiederverwerten deren Lösungen. Dabei wird davon ausgegangen, dass sich die optimale 
Lösung des Gesamtproblems aus den optimalen Lösungen seiner Teilprobleme zusammensetzt. \\
Nebst Gebieten der Mathematik findet Dynamic Programming auch in der Computerprogrammierung Anwendung. 
So basiert auch einer der ältesten Algorithmen zum Abgleichen von Gensequenzen in der Bioinformatik 
auf dieser Methode.
\end{abstract}
%

\section{Dynamic Programming}
\subsection{Einleitung}

Der Begriff "\textit{Dynamic Programming}" wurde von Richard Bellman (* 29.8.1920 Brooklyn, NY; † 19.3.1984 Los Angeles, CA) eingeführt. Bellman entwickelte ab 1949 für die RAND Corporation in Santa Monica, ein von der Airforce finanziertes Forschungsinstitut, mit einigen weiteren Mathematikern ein entsprechendes Prinzip, das ursprünglich in der Regelungstheorie Anwendung findet. Der Grundgedanke hinter der dynamischen Programmierung wird heutzutage aber auch zur Entwicklung von Algorithmen benutzt.

\subsection{Vorgehensweise}

Der Grundgedanke der dynamischen Programmierung liegt darin, ein Problem so in Teilprobleme zu zerlegen, dass sich seine optimale Lösung aus den optimalen Lösungen der Teilprobleme zusammensetzt. Die einzelnen Teilprobleme sind aufgrund ihrer geringeren Komplexität jeweils leichter zu lösen und können anschliessend zu einem nächstgrösseren Teilproblem zusammengesetzt werden, dessen Lösung wiederum aus den entsprechenden Resultaten ermittelt werden kann. Dabei werden bereits ermittelte Lösungen für Teilprobleme zwischengespeichert, damit jedes Teilproblem nur einmal gelöst werden muss.

\subsection{Voraussetzungen}

Probleme, die mit Dynamic Programming gelöst werden sollen, müssen bestimmte, durch die Methodik bedingte, Eigenschaften aufweisen:

\subsubsection{Teilbarkeit}

Jedes Problem sollte in kleinere Probleme aufgeteilt werden können. Die jeweiligen Teilprobleme sollten dabei immer eine ähnliche Struktur aufweisen und einfach parametrisierbar sein. Normalerweise sind auch die Teilprobleme wiederum aufteilbar. Wichtig ist ausserdem, dass die aus einer Aufteilung resultierenden Teilprobleme stets eine geringere Komplexität aufweisen als das nächst übergeordnete Problem. 

\subsubsection{Optimale Substruktur}

Ein Problem weist eine optimale Substruktur auf, wenn seine optimale Lösung sich aus den optimalen Lösungen seiner Teilprobleme zusammensetzt. Es darf also nicht möglich sein, dass sich während der Problemlösung die Verwendung einer nicht optimalen Lösung für ein Teilproblem positiv auf die Lösung des Gesamtproblems auswirkt.

\subsubsection{Überlappende Teilprobleme}

Da der Vorteil von Dynamic Programming gegenüber anderen Herangehensweisen (wie zum Beispiel einer Lösung durch reine Rekursion) aus der Speicherung von gelösten Teilproblemen besteht, ist der Einsatz dieser Methode nur von Vorteil, wenn während der Lösung eines Problems mehrmals die selben Teilprobleme auftreten.

\subsection{Anwendung in der Computerprogrammierung}

In der Computerprogrammierung kann das Prinzip der dynamischen Programmierung auf viele Probleme angewendet werden. Beispiele hierfür sind unter anderem die Sequence Alignment-Algorithmen von \textit{Needleman und Wunsch} und \textit{Smith und Waterman}, die später in dieser Arbeit noch genauer vorgestellt werden.

\subsection{Top-Down und Bottom-Up}

Probleme, auf die Dynamic Programming anwendbar ist, lassen sich durch ihre Aufteilbarkeit in ähnliche Subprobleme meist durch Rekursion abbilden. Eine solche Implementation kann oft ohne grosse Änderungen durch \textit{Memoization} in einen Dynamic Programming-Algorithmus umwandeln. Diesen Ansatz nennt man, da der Weg der Lösungssuche beim Hauptproblem beginnt und in die Teilprobleme "absteigt" \textit{Top-Down}. 

Mit der gegenteiligen Vorgehensweise, \textit{Bottom-Up}, formuliert man das Problem so um, dass - beispielsweise in einer Schleife - zuerst die "tiefsten" Teilprobleme gelöst werden. Dieser Fall ist programmiertechnisch oft interessanter, da sich so die Anzahl der nötigen Methodenaufrufe (und entsprechender Speicherbedarf auf dem Stack) weiter begrenzen lassen.

\subsection{Beispiel: Die Fibonacci-Funktion}

\subsubsection{Übersicht}

Die \textit{Fibonacci-Folge} ist eine rekursiv definierte, unendliche Folge von Zahlen. Sie ist nach Leonardo Fibonacci benannt, der sie zum Abbilden einer Kaninchenpopulation benutzte. Jedes Element der Fibonacci-Folge lässt sich durch die Summe der beiden vorhergehenden Zahlen errechnen, wobei die ersten zwei Elemente (meist 0 und 1) vorgegeben werden.
Als \textit{Fibonacci-Funktion} bezeichnen wir hier eine mathematische Funktion, die für ein gegebenes $n$ die zugehörige Zahl $F_n$ aus der Fibonacci-Folge zurückliefert.

\subsubsection{Präsentation}
Die mathematische Definition der Fibonacci-Funktion sieht folgendermassen aus:

\begin{equation}
	F_n = 
	\begin{cases}
		0 & \mbox{für } n = 1 \\
		1 & \mbox{für } n = 2 \\
		F_{n-1} + F_{n-2} & \mbox{für } n > 2 \\
	\end{cases}
	\label{eq:Fibonacci}
\end{equation}


\subsubsection{Rekursive Implementation der Fibonacci-Funktion}

Die Fibonacci-Funktion lässt sich ohne grossen Aufwand direkt nach der Gleichung~\ref{eq:Fibonacci} implementieren. Der rekursive Ansatz führt aber zu einer exponentiell anwachsenden Anzahl an Funktionsaufrufen (109 für $n = 10$, 13529 für $n = 20$) und weist damit eine sehr schlechte Skalierbarkeit auf.

\begin{algorithm}[!h]
\caption{Fibonacci-Funktion (rekursiv)}\label{alg:FibonacciRekursiv}
\begin{algorithmic}
	\Function{Fibonacci}{n}
		\If{$n < 1$}
			\State throw an error 
		\EndIf
		\If{$n == 1$}
			\State \textbf{return} $1$
		\ElsIf{$n == 2$}
			\State \textbf{return} $2$
		\Else 
			\State \textbf{return} $Fibonacci(n-1) + Fibonacci(n-2)$
		\EndIf
	\EndFunction
\end{algorithmic}
\end{algorithm}

\subsubsection{Implementation mit Dynamic Programming}

Um diesen immensen Rechenaufwand bei der Berechnung von $F_n$ zu vermeiden, lohnt es sich, bei der Implementation auf Dynamic Programming zurückzugreifen. Wie bereits beschrieben, müssen Probleme bestimmte Eigenschaften aufweisen, um effizient mit dieser Methode gelöst werden zu können. Betrachtet man die Definition der Fibonacci-Folge unter diesen Gesichtspunkten, erkennt man, dass von ihr alle aufgeführten Kriterien erfüllt werden:

\begin{itemize}
	\item{Die Teilbarkeit lässt sich direkt aus Gleichung~\ref{eq:Fibonacci} ableiten: Jede Zahl der Folge wird aus den zwei vorhergehenden Zahlen (also den "Teilproblemen") errechnet. }
	\item{Dass diese Teilprobleme während der Lösung des Problems mehrmals berechnet werden müssen, fällt beim Betrachten der Abbildung~\ref{fig:FibonacciTree} direkt ins Auge: $F_1$ wird für $n = 9$ beispielsweise 13 mal ermittelt.}
	\item{Die optimale Substruktur ist in diesem Beispiel klar gegeben, da es sich um eine exakte Berechnung (und nicht ein Optimierungsproblem) handelt. Es existiert für jedes $n$ nur exakt eine richtige Lösung und die setzt sich immer aus den richtigen Lösungen der vorhergehenden Zahlen zusammen.}
\end{itemize}

Der einfachste Weg, die Funktion mit Dynamic Programming umzusetzen, liegt in diesem Fall im Top-Down-Ansatz: Durch die Verwendung von \textit{Memoization} lässt sich das wiederholte Berechnen von bereits ermittelten Fibonacci-Zahlen vermeiden. Der Nachteil dieser Methode ist jedoch, dass durch die rekursive Formulierung immer noch beachtlich viele Funktionsaufrufe erfolgen, und somit immer noch Ressourcen (beispielsweise Speicherplatz auf dem Stack) "verschwendet" werden. Zudem benötigt die so geschriebene Funktion immer noch $O(n)$ Speicherplatz zum Speichern der errechneten Teillösungen.

\begin{algorithm}[!h]
\caption{Fibonacci-Funktion (Top-Down)}\label{alg:FibonacciTopDown}
\begin{algorithmic}
	\State $cache \gets$ Array[ ] of Integer
	\Function{Fibonacci}{n}
		\If{$n < 1$}
			\State throw an error 
		\EndIf
		\If{$n == 1$}
			\State \textbf{return} $0$
		\ElsIf{$n == 2$}
			\State \textbf{return} $1$
		\Else
			\If{$length(cache) < n$}
				\State Extend $cache$ to length $n$
			\EndIf
			\If{$cache[n] is not set$}
				\State $cache[n] \gets Fibonacci(n-1) + Fibonacci(n-2)$
			\EndIf
		\EndIf
		\State \textbf{return} $cache[n]$
	\EndFunction
\end{algorithmic}
\end{algorithm}

\begin{sidewaysfigure}
\begin{tikzpicture}[every node/.style={font=\fontsize{5}{5}\selectfont,rectangle, draw=black, rounded corners=1mm, fill=white, circular drop shadow, text centered, anchor=north, text=black},
level distance=0.5cm,
growth parent anchor=south,
level 1/.style={sibling distance=10cm},
level 2/.style={sibling distance=5cm},
level 3/.style={sibling distance=2.5cm},
level 4/.style={sibling distance=1.5cm},
level 5/.style={sibling distance=0.7cm},
level 6/.style={sibling distance=0.35cm},
level 7/.style={sibling distance=0.35cm}]
	\node {9} [->]
		child { node{7}
			child { node{5}
				child { node{3}
					child { node{1} }
					child { node{2} }
				}
				child { node{4}
					child { node{2} }
					child { node{3}
						child { node{1} }
						child { node{2} }
					}
				}
			}
			child { node{6}
				child { node{4}
					child { node{2} }
					child { node{3}
						child { node{1} }
						child { node{2} }
					}
				}
				child { node{5}
					child { node{3}
						child { node{1} }
						child { node{2} }
					}
					child { node{4}
						child { node{2} }
						child { node{3}
							child { node{1} }
							child { node{2} }
						}
					}
				}
			}
		}
		child { node{8}
			child { node{6}
				child { node{4}
					child { node{2} }
					child { node{3}
						child { node{1} }
						child { node{2} }
					}
				}
				child { node{5}
					child { node{3}
						child { node{1} }
						child { node{2} }
					}
					child { node{4}
						child { node{2} }
						child { node{3}
							child { node{1} }
							child { node{2} }
						}
					}
				}
			}
			child { node{7}
				child { node{5}
					child { node{3}
						child { node{1} }
						child { node{2} }
					}
					child { node{4}
						child { node{2} }
						child { node{3}
							child { node{1} }
							child { node{2} }
						}
					}
				}
				child { node{6}
					child { node{4}
						child { node{2} }
						child { node{3}
							child { node{1} }
							child { node{2} }
						}
					}
					child { node{5}
						child { node{3}
							child { node{1} }
							child { node{2} }
						}
						child { node{4}
							child { node{2} }
							child { node{3}
								child { node{1} }
								child { node{2} }
							}
						}
					}
				}
			}
		}
	;
\end{tikzpicture}
\caption{Dieser Baum veranschaulicht die Anzahl der Funktionsaufrufe einer rekursiven Implementation der Fibonacci-Funktion für die Zahl 9. Jedes Element des Baums stellt einen Funktionsaufruf dar.}
\label{fig:FibonacciTree}
\end{sidewaysfigure}

Ein anderer Weg, die Funktion mit Dynamic Programming umzusetzen, ist die Bottom-Up-Methode. Eine solche Funktion beginnt anstelle des eigentlichen Problems ($F_n$) mit der Berechnung der kleinsten Teilprobleme ($F_1$ und $F_2$) und arbeitet sich nach und nach zum grössten Problem vor. Diese Vorgehensweise lässt sich ohne die Verwendung von Rekursion umsetzen und erlaubt im Falle der Fibonacci-Zahlen sogar das Weglassen eines kompletten Caches, um Speicher zu sparen. Die Fibonacci-Funktion lässt sich somit zu $O(n)$ Rechenaufwand und $O(1)$ Speicherbedarf reduzieren.

\begin{algorithm}[!h]
\caption{Fibonacci-Funktion (Bottom-Up)}\label{alg:FibonacciBottomUp}
\begin{algorithmic}
	\Function{Fibonacci}{n}
		\If{$n < 1$}
			\State throw an error 
		\EndIf
		\If{$n == 1$}
			\State \textbf{return} $0$
		\ElsIf{$n == 2$}
			\State \textbf{return} $1$
		\Else
			\State $a \gets 0$
			\State $b \gets 1$
			\For{$i \gets 2\dots{}n$}
				\State $c \gets a$
				\State $a \gets b$
				\State $b \gets c+a$
			\EndFor
			\State \textbf{return} $b$
		\EndIf
	\EndFunction
\end{algorithmic}
\end{algorithm}

%\begin{figure}[h]
\begin{figure}
\begin{center}
\begin{tikzpicture}
 \tikzstyle{every node}=[draw,circle]
\node[circle, fill=black!30] (2) at (0,0){2};
\node (4) at +(2, 0){4};
\node (6) at +(5,0){6};
\node (8) at +(7,0){8};
\node (10) at +(9,0){10};
\node[circle, fill=black!30] (1) at (-2,1){1};
\node (3) at (1,1){3};
\node (5) at (3.5,1){5};
\node (7) at (6,1){7};
\node (9) at (8,1){9};
\foreach \from/\to in {1/3,2/3,2/4,3/4,3/5,4/5,4/6,5/6,5/7,6/7,6/8,7/8,7/9,8/9,8/10,9/10}
\draw[->](\from)--(\to);
\end{tikzpicture}
\caption{Eine grafische Darstellung einer Bottom-Up-Implementation. Jedes Element entspricht einem Schleifendurchlauf.}
\end{center}
\end{figure}

\section{Anwendung in Sequence Alignment}

\subsection{Übersicht}

\textit{Sequence Alignment} ist ein Thema der Bioinformatik und behandelt das Vergleichen von Zeichenketten. Entsprechende Anwendungen werden zur Analyse  und zum Bestimmen von Ähnlichkeiten zwischen DNA- oder RNA-Ketten benutzt. Diese Ketten werden normalerweise als Zeichenkette (String) abgebildet; die verschiedenen Buchstaben stellen in diesem Fall die Nukleotiden dar (beispielsweise A für Adenin). Zum Thema Sequence Alignment existieren verschiedene Algorithmen unterschiedlicher Komplexität, von denen sich diese Arbeit auf zwei sehr grundlegende konzentriert.

\subsection{Pairwise Alignment}

Der wohl älteste Lösungsansatz auf dem Gebiet der Sequence Alignment-Probleme ist das \textit{Pairwise Alignment}, in dem die gegebenen Strings Zeichen um Zeichen verglichen werden. Diese Methodik lässt zwar lediglich das Abgleichen zweier Strings zu, sie lässt sich dafür effizienter umsetzen als komplexere Herangehensweisen. 

Da das Ziel von Sequence Alignment in einem Vergleich (und nicht in einer Mustersuche) liegt, wird ein entsprechender Algorithmus immer ein Resultat zurückliefern. Die Treffer eines Pairwise Alignment-Algorithmus können daher in den verglichenen Strings eingeschobene Lücken (Gaps) oder nicht übereinstimmende Positionen enthalten.

Typischerweise benutzen Pairwise Alignment-Algorithmen einen numerischen Wert (Score), anhand dessen sich die Qualität von möglichen Angleichungen erschliessen lässt. Dieser Wert kann mit unterschiedlichen Methoden bestimmt werden; ein Beispiel für einen Score ist die \textit{Edit Distance}: Dieser Wert entspricht den Anzahl Schritten, die nötig sind, um eine Zeichenkette in eine andere zu überführen. Für die Edit Distance wäre also ein möglichst kleiner Wert erwünscht. Ein Algorithmus wird, nachdem alle Berechnungen getroffen wurden, seine Resultate anhand der berechneten Scores beurteilen und jeweils nur die "besten" zurückliefern.

\subsection{Globale und lokale Alignmentmethoden}

Es existieren mehrere Ansätze für Pairwise Alignment, von denen wir wiederum lediglich auf die zwei grundlegensten eingehen werden: \textit{Global Alignment} und \textit{Local Alignment}.

\subsubsection{Global Alignment}

\textit{Global Alignment} ist besonders nützlich, wenn zwei etwa gleich lange Zeichenketten verglichen werden sollen. Global Alignment-Algorithmen versuchen, jedes einzelne Zeichen der beiden Ketten abzugleichen, und strecken die resultierenden Strings auf die selbe Länge.

\subsubsection{Local Alignment}

\textit{Local Alignment} hingegen wird zum Suchen bestimmter Sequenzen in einem String verwendet. Local Alignment-Algorithmen müssen nicht zwingend jedes Zeichen der beiden Ketten abgleichen und liefern Regionen mit grösstmöglicher Ähnlichkeit zurück.

\subsection{Algorithmus von Needleman und Wunsch (1970)}

Die von Saul B. Needleman und Christian D. Wunsch veröffentlichte Methode, die wir hier vorstellen, ist ein auf Pairwise Alignment basierender Global Alignment-Algorithmus und verwendet das Konzept von Dynamic Programming zur Berechnung der möglichen Alignments.

Die Bewertung von möglichen Resultaten erfolgt anhand einer \textit{Kosten-Nutzen-Rechnung}:
Für den Algorithmus wird eine Funktion $\sigma$ definiert, deren Rückgabewert den Nutzen (> 0) eines gleichen Zeichens oder die Kosten (< 0) eines "falschen" Zeichens repräsentiert. Ausserdem setzt die Variable $\gamma$, deren Wert den Kosten für das Einschieben einer Lücke in einen der Strings entspricht. Die Summe der Scores aller Einzelpositionen ergibt damit den Score einer Anordnung, der im optimalen Fall maximal sein muss.

Will man nun die zwei Strings x und y vergleichen, kann man den Score S des optimalen Alignments $A_{opt}$ von $x_{1\dots{}i}$ und $y_{1\dots{}j}$ rekursiv definieren:

\begin{equation}
S(i,j) = max 
\begin{cases}
	S(i-1,j-1) + \sigma(x_{i}, y_{j}), \\
	S(i-1,j) + \gamma, \\
	S(i,j-1) + \gamma \\
\end{cases}
\label{eq:NeedlemanWunsch}
\end{equation}

Die optimale Substruktur lässt indirekt beweisen: \\
Angenommen, es existiert ein optimales Alignment $A_{opt}(i,j)$, das ein nicht optimales Teilalignment $A'(i-1,j-1)$ beinhaltet:
$$S(A_{opt}(i,j)) = S(A'(i-1,j-1)) + \sigma(i,j),$$
$$\exists A_{opt}(i-1,j-1) \text{, sodass } S(A_{opt}(i-1,j-1)) > S(A'(i-1,j-1))$$

Daraus ergibt sich:
$$S(A_{opt}(i-1,j-1)) + \sigma(i+j) > S(A'(i-1,j-1)) + \sigma(i,j)$$
$$\Rightarrow S(A_{opt}(i-1,j-1)) + \sigma(i+j) > S(A_{opt}(i,j))$$

Dies stellt einen Widerspruch zur Annahme dar, dass $S(A_{opt}(i,j))$ optimal sei.
\begin{flushright}
	$\Box$
\end{flushright}

Dieser Beweis lässt sich analog auf $S(i-1,j)$ oder $S(i,j-1)$ und $\gamma$ anwenden.

\subsection{Implementation}

Wie auch schon im Beispiel der Fibonacci-Folge lässt sich die oben beschriebene Funktion zwar rekursiv umsetzen, der Rechenaufwand einer solchen Implementation würde aber mit wachsender Länge der zu vergleichenden Zeichenfolgen exponentiell anwachsen. Zur Verbesserung seiner Effizienz wird daher im Needleman-Wunsch-Algorithmus eine Bottom-Up-Umsetzung von Dynamic Programming verwendet. Im Unterschied zur Fibonacci-Folge reicht dabei aber ein eindimensionaler Cache nicht mehr aus, um die errechneten Resultate zu speichern.

Der Algorithmus erstellt stattdessen eine Tabelle aus Scorewerten, deren Spalten und Zeilen je ein Zeichen der jeweiligen Zeichenketten x und y entsprechen; die jeweils erste Zeile bzw. Spalte lässt man dabei frei. 
In den Abbildungen~\ref{fig:NWMatrixLeer}ff. ist als Beispiel die Entwicklung einer solchen Matrix für die Strings x = "TCG" und y = "ATCGC" abgebildet. 
Für die Scoreberechnung verwenden wir im Beispiel einen Nutzen von $\sigma = 1$ übereinstimmenden Zeichen, $\sigma = -1$ als Kosten für ein Paar verschiedener Zeichen und $\gamma = -2$ als Kosten für eine eingefügte Lücke.

Das erste Feld oben links stellt den Initialzustand dar und wird auf 0 gesetzt. Anschliessend daran werden horizontal und vertikal die kumulierten Gapkosten ($\gamma$) eingetragen (siehe Abbildung~\ref{fig:NWMatrixGapKosten}).


\begin{figure}[h]
	\begin{minipage}[t]{0.45\linewidth}
		\begin{tikztable}
			\columns{5}
			\rows{7}
			\begin{tikzrow}
				\tikznocell
				\tikznocell
				\tikzcell{T}
				\tikzcell{C}
				\tikzcell{G}
			\end{tikzrow}
			\begin{tikzrow}
				\tikznocell
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{A}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{T}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{C}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{G}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{C}
			\end{tikzrow}
		\end{tikztable}
		\caption{Die leere Matrix für die Strings "TCG" und "ATCGC".}
		\label{fig:NWMatrixLeer}
	\end{minipage}
	\hspace{\fill}
	\begin{minipage}[t]{0.45\linewidth}
		\begin{tikztable}
			\columns{5}
			\rows{7}
			\begin{tikzrow}
				\tikznocell
				\tikznocell
				\tikzcell{T}
				\tikzcell{C}
				\tikzcell{G}
			\end{tikzrow}
			\begin{tikzrow}
				\tikznocell
				\tikzcell{0}
				\tikzcell{-2}
				\tikzcell{-4}
				\tikzcell{-6}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{A}
				\tikzcell{-2}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{T}
				\tikzcell{-4}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{C}
				\tikzcell{-6}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{G}
				\tikzcell{-8}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{C}
				\tikzcell{-10}
			\end{tikzrow}
		\end{tikztable}
		\caption{Nach dem Auffüllen der Gapkosten.}
		\label{fig:NWMatrixGapKosten}
	\end{minipage}
\end{figure}

Alle übrigen Felder werden nun gemäss der rekursiven Definition errechnet. Der Algorithmus durchläuft in einer Schleife von oben links nach unten rechts alle Positionen. In jeder Zelle sind drei Werte möglich:

\begin{enumerate}
	\item{Die Kosten/Nutzen $\sigma$ der Zeichen in der zugehörigen Zeile/Spalte, addiert mit dem Wert des Feldes links über der aktuellen Position}
	\item{Der Wert des Feldes unmittelbar darüber plus Gapkosten $\gamma$}
	\item{Der Wert des Feldes unmittelbar links plus Gapkosten $\gamma$}
\end{enumerate}

\begin{figure}[h]
	\begin{minipage}[t]{0.3\linewidth}
		\begin{tikztable}
			\columns{3}
			\rows{3}
			\begin{tikzrow}
				\tikznocell
				\tikznocell
				\tikzcell{T}
			\end{tikzrow}
			\begin{tikzrow}
				\tikznocell
				\tikzcell{0}
				\tikzcell{-2}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{A}
				\tikzcell{-2}
				\nodecolor{blue}
				\arrowcolor{blue}
				\tikzcell{-1}
				\ularrow
				\nodecolor{black}
				\arrowcolor{red}
			\end{tikzrow}
		\end{tikztable}
		$$S(i-1,j-1) + \sigma(x_{i}, y_{j})$$
		$$0 + (-1) = -1$$
	\end{minipage}
	\hspace{\fill}
	\begin{minipage}[t]{0.3\linewidth}
		\begin{tikztable}
			\columns{3}
			\rows{3}
			\begin{tikzrow}
				\tikznocell
				\tikznocell
				\tikzcell{T}
			\end{tikzrow}
			\begin{tikzrow}
				\tikznocell
				\tikzcell{0}
				\tikzcell{-2}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{A}
				\tikzcell{-2}
				\nodecolor{orange}
				\arrowcolor{orange}
				\tikzcell{-4}
				\larrow
				\nodecolor{black}
				\arrowcolor{red}
			\end{tikzrow}
		\end{tikztable}
		$$S(i-1,j) + \gamma$$
		$$(-2) + (-2) = -4$$
	\end{minipage}
	\hspace{\fill}
	\begin{minipage}[t]{0.3\linewidth}
		\begin{tikztable}
			\columns{3}
			\rows{3}
			\begin{tikzrow}
				\tikznocell
				\tikznocell
				\tikzcell{T}
			\end{tikzrow}
			\begin{tikzrow}
				\tikznocell
				\tikzcell{0}
				\tikzcell{-2}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{A}
				\tikzcell{-2}
				\nodecolor{green}
				\arrowcolor{green}
				\tikzcell{-4}
				\uarrow
				\nodecolor{black}
				\arrowcolor{red}
			\end{tikzrow}
		\end{tikztable}
		$$S(i,j-1) + \gamma$$
		$$(-2) + (-2) = -4$$
	\end{minipage}
	\caption{Die möglichen Scorewerte für das erste Feld.}
	\label{fig:NWMatrixMöglicheScores}
\end{figure}

Entsprechend Gleichung~\ref{eq:NeedlemanWunsch} wird der jeweils grösste dieser drei Werte benutzt. Zusätzlich zum Score wird auch die Zelle abgespeichert, aus welcher sich der Wert ergeben hat (in Abbildung~\ref{fig:NWMatrixScoresPfeile} als Pfeile dargestellt). Kann der maximale Score aus mehreren Zellen abgeleitet werden, werden alle gespeichert. In der Praxis wird dies meist über eine oder mehrere zusätzliche Matrizen erreicht.

Sind alle Felder der Tabelle ausgefüllt, kann an der letzten Position (unten rechts) der Score des besten Alignments abgelesen werden. Es ist möglich, dass der Needleman-Wunsch-Algorithmus mehrere Resultate zurückliefert, sofern diese den selben Score aufweisen. Die Anordnung der Zeichen (und eventuell Lücken) kann rückwärts anhand der gespeicherten Ausganspunkte konstruiert werden; Bewegungen entlang der diagonalen Achse bedeuten dabei eine Gegenüberstellung der zwei zugehörigen Zeichen (der entsprechenden Zeile/Spalte), Bewegungen nach links und oben stehen für eine eingefügte Lücke in der horizontalen bzw. vertikalen Zeichenfolge. Das Resultierende Alignment im hier verwendeten Beispiel ist in den Abbildungen \ref{fig:NWMatrixScores} und \ref{fig:NWResult} dargestellt. 

\begin{figure}[!h]
	\begin{minipage}[t]{0.45\linewidth}
		\begin{tikztable}
			\columns{5}
			\rows{7}
			\begin{tikzrow}
				\tikznocell
				\tikznocell
				\tikzcell{T}
				\tikzcell{C}
				\tikzcell{G}
			\end{tikzrow}
			\begin{tikzrow}
				\tikznocell
				\tikzcell{0}
				\tikzcell{-2}
				\larrow
				\tikzcell{-4}
				\larrow
				\tikzcell{-6}
				\larrow
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{A}
				\tikzcell{-2}
				\uarrow
				\tikzcell{-1}
				\ularrow
				\tikzcell{-3}
				\ularrow
				\larrow
				\tikzcell{-5}
				\ularrow
				\larrow
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{T}
				\tikzcell{-4}
				\uarrow
				\tikzcell{-1}
				\ularrow
				\tikzcell{-2}
				\ularrow
				\tikzcell{-4}
				\ularrow
				\larrow
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{C}
				\tikzcell{-6}
				\uarrow
				\tikzcell{-3}
				\uarrow
				\tikzcell{0}
				\ularrow
				\tikzcell{-2}
				\larrow
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{G}
				\tikzcell{-8}
				\uarrow
				\tikzcell{-5}
				\uarrow
				\tikzcell{-4}
				\ularrow
				\tikzcell{1}
				\ularrow
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{C}
				\tikzcell{-10}
				\uarrow
				\tikzcell{-7}
				\uarrow
				\tikzcell{-4}
				\ularrow
				\tikzcell{-1}
				\uarrow
			\end{tikzrow}
		\end{tikztable}
		\caption{Scorewerte und Ursprungszellen der kompletten Tabelle.}
		\label{fig:NWMatrixScoresPfeile}
	\end{minipage}
	\hspace{\fill}
	\begin{minipage}[t]{0.45\linewidth}
		\begin{tikztable}
			\columns{5}
			\rows{7}
			\begin{tikzrow}
				\tikznocell
				\tikznocell
				\tikzcell{T}
				\tikzcell{C}
				\tikzcell{G}
			\end{tikzrow}
			\begin{tikzrow}
				\tikznocell
				\cellcolor{yellow}
				\tikzcell{0}
				\cellcolor{white}
				\tikzcell{-2}
				\tikzcell{-4}
				\tikzcell{-6}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{A}
				\cellcolor{yellow}
				\tikzcell{-2}
				\uarrow
				\cellcolor{white}
				\tikzcell{-1}
				\tikzcell{-3}
				\tikzcell{-5}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{T}
				\tikzcell{-4}
				\cellcolor{yellow}
				\tikzcell{-1}
				\ularrow
				\cellcolor{white}
				\tikzcell{-2}
				\tikzcell{-4}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{C}
				\tikzcell{-6}
				\tikzcell{-3}
				\cellcolor{yellow}
				\tikzcell{0}
				\ularrow
				\cellcolor{white}
				\tikzcell{-2}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{G}
				\tikzcell{-8}
				\tikzcell{-5}
				\tikzcell{-4}
				\cellcolor{yellow}
				\tikzcell{1}
				\ularrow
				\cellcolor{white}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{C}
				\tikzcell{-10}
				\tikzcell{-7}
				\tikzcell{-4}
				\cellcolor{yellow}
				\tikzcell{-1}
				\uarrow
				\cellcolor{white}
			\end{tikzrow}
		\end{tikztable}
		\caption{Das optimale Alignment der beiden Zeichenfolgen.}
		\label{fig:NWMatrixScores}
	\end{minipage}


	{ 
		\Huge \hfill
		\begin{tabularx}{5cm}{>{\centering\arraybackslash}p{1cm}>{\centering\arraybackslash}p{1cm}>{\centering\arraybackslash}p{1cm}>{\centering\arraybackslash}p{1cm}>{\centering\arraybackslash}p{1cm}}
			A & T & C & G & C \\
			  & | & | & | & \\
			- & T & C & G & -
		\end{tabularx}
		\hfill
	}
	$$S(x,y) = (-2) + 1 + 1 + 1 + (-2) = -1$$
	\caption{Das ausnotierte optimale globale Alignment von x und y. Bindestriche stehen für eingefügte Gaps.}
	\label{fig:NWResult}
\end{figure}

Die Methode von Needleman und Wunsch weist zwar einen Performancevorteil gegenüber einer direkten rekursiven Implementation auf, ist aber im Vergleich zu neueren Sequence-Alignment-Algorithmen dennoch sehr ineffizient. Wie der Matrix entnommen werden kann, nehmen sowohl Speicherverbrauch als auch Rechenaufwand mit $O(nm)$ zu, was einen Vergleich grösserer Sequenzen verunmöglicht. 

Als Beispiel kann von zwei je 10'000 Zeichen langen Strings ausgegangen werden: Jede Zelle sollte über genug Speicher für eine maximale Nutzen- oder Kostensumme verfügen. In unserem Beispiel wurde $\gamma = -2$ verwendet, was bedeutet, dass eine Zelle die Zahl $10'000×(-2) = -20'000$ enthalten kann, was mit einem unsigned Short (2 Bytes, $−32,768$ bis $32,767$) möglich ist. Die  Matrix besteht dabei aus $10'001^2$ Zellen à 2 Bytes, was in etwa 190 Megabytes entspricht: $\frac{2×(10'001^2)}{2^{20}} \approx 190.7730$

Ganze Genome können mit diesem Algorithmus daher nicht verglichen werden, da sie meist viel zu viele Positionen enthalten (das menschliche Genon beispielsweise besteht aus ca. $3.27×10^9$ Basenpaaren\cite{bib:wiki:genom}). 

Eine Pseudocode-Version des Needleman-Wunsch-Algorithmus mit einer Depth-First-Traceback-Routine ist unter Algorithmus~\ref{alg:NW} abgebildet. In dieser Notation wird davon ausgegangen, dass der Index aller Arrays und Strings bei 0 beginnt.

\subsection{Algorithmus von Smith und Waterman (1981)}

Temple F. Smith und Michael S. Waterman entwickelten auf Basis der Needleman-Wunsch-Methode einen Algorithmus zur Ermittlung lokaler Alignments. Wendet man die ursprüngliche Kosten-Nutzen-Rechnung auf lokale Alignments an, muss man einige Änderungen berücksichtigen: Da lediglich lokale Ähnlichkeiten gesucht werden (die nicht zwingend mit dem ersten Zeichen beginnen), werden sämtliche möglichen Teilalignments mit negativen Scorewerten ignoriert. Ausserdem muss das gesuchte Resultat nicht bis zur letzten Position beider Zeichenketten durchlaufen; ein optimales lokales Alignment läuft also nur bis zu genau dem Moment, an dem sein kumulierter Score maximal ist.

Der Smith-Waterman-Algorithmus ergänzt daher die Regeln des Originals um einen weiteren Punkt: Zusätzlich zu den üblichen Werten kann jede Zelle der errechneten Tabelle den Wert 0 annehmen, was bedeutet, dass kein Feld der Matrix einen negativen Wert annimmt. Für Positionen, auf die dieser Fall zutrifft, wird keine Ursprungszelle gespeichert, da sie lediglich ein möglicher Start (aber kein Bestandteil) eines optimalen lokalen Alignments sind. Die erweiterte rekursive Definition des Alignmentscores lautet demnach wiefolgt:


\begin{equation}
S(i,j) = max 
\begin{cases}
	0, \\
	S(i-1,j-1) + \sigma(x_{i}, y_{j}), \\
	S(i-1,j) + \gamma, \\
	S(i,j-1) + \gamma \\
\end{cases}
\label{eq:SmithWaterman}
\end{equation}

Was sich im Algorithmus von Smith und Waterman ebenfalls ändert, ist die Methode, mit der die Alignment-Strings aus der ausgefüllten Matrix rekonstruiert werden: Da der Algorithmus nach lokalen Alignments sucht, startet die Traceback-Routine an den Zellen mit dem höchsten Score und läuft lediglich bis zur ersten Nullstelle, statt diagonal über die ganze Matrix zu laufen. 

Die Abbildungen~\ref{fig:SWMatrixScoresPfeile}ff. veranschaulichen das Resultat des Smith-Waterman-Algorithmus auf die Zeichenketten des Needleman-Wunsch-Beispieles. 

Die minimalen Änderungen, die nötig sind, um die ursprüngliche Herangehensweise zum Suchen lokaler Ähnlichkeiten zu verwenden, führen dazu, dass der Algorithmus von Smith und Waterman in Bezug auf Skalierbarkeit die selben Vor- und Nachteile wie sein Vorgänger mit sich bringt.


\begin{figure}[!h]
	\begin{minipage}[t]{0.45\linewidth}
		\begin{tikztable}
			\columns{5}
			\rows{7}
			\begin{tikzrow}
				\tikznocell
				\tikznocell
				\tikzcell{T}
				\tikzcell{C}
				\tikzcell{G}
			\end{tikzrow}
			\begin{tikzrow}
				\tikznocell
				\tikzcell{0}
				\tikzcell{0}
				\tikzcell{0}
				\tikzcell{0}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{A}
				\tikzcell{0}
				\tikzcell{0}
				\tikzcell{0}
				\tikzcell{0}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{T}
				\tikzcell{0}
				\tikzcell{1}
				\ularrow
				\tikzcell{0}
				\tikzcell{0}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{C}
				\tikzcell{0}
				\tikzcell{0}
				\tikzcell{2}
				\ularrow
				\tikzcell{0}
				\larrow
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{G}
				\tikzcell{0}
				\tikzcell{0}
				\tikzcell{0}
				\uarrow
				\tikzcell{3}
				\ularrow
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{C}
				\tikzcell{0}
				\tikzcell{0}
				\tikzcell{1}
				\ularrow
				\tikzcell{1}
				\uarrow
			\end{tikzrow}
		\end{tikztable}
		\caption{Scorewerte und Ursprungszellen der kompletten Tabelle.}
		\label{fig:SWMatrixScoresPfeile}
	\end{minipage}
	\hspace{\fill}
	\begin{minipage}[t]{0.45\linewidth}
		\begin{tikztable}
			\columns{5}
			\rows{7}
			\begin{tikzrow}
				\tikznocell
				\tikznocell
				\tikzcell{T}
				\tikzcell{C}
				\tikzcell{G}
			\end{tikzrow}
			\begin{tikzrow}
				\tikznocell
				\tikzcell{0}
				\tikzcell{0}
				\tikzcell{0}
				\tikzcell{0}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{A}
				\cellcolor{yellow}
				\tikzcell{0}
				\cellcolor{white}
				\tikzcell{0}
				\tikzcell{0}
				\tikzcell{0}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{T}
				\tikzcell{0}
				\cellcolor{yellow}
				\tikzcell{1}
				\cellcolor{white}
				\ularrow
				\tikzcell{0}
				\tikzcell{0}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{C}
				\tikzcell{0}
				\tikzcell{0}
				\cellcolor{yellow}
				\tikzcell{2}
				\cellcolor{white}
				\ularrow
				\tikzcell{0}
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{G}
				\tikzcell{0}
				\tikzcell{0}
				\tikzcell{0}
				\cellcolor{yellow}
				\tikzcell{3}
				\cellcolor{white}
				\ularrow
			\end{tikzrow}
			\begin{tikzrow}
				\tikzcell{C}
				\tikzcell{0}
				\tikzcell{0}
				\tikzcell{1}
				\tikzcell{1}
			\end{tikzrow}
		\end{tikztable}
		\caption{Das optimale lokale Alignment der beiden Zeichenfolgen.}
		\label{fig:SWMatrixScores}
	\end{minipage}


	{ 
		\Huge \hfill
		\begin{tabularx}{3cm}{>{\centering\arraybackslash}p{1cm}>{\centering\arraybackslash}p{1cm}>{\centering\arraybackslash}p{1cm}}
			T & C & G \\
			| & | & | \\
			T & C & G
		\end{tabularx}
		\hfill
	}
	$$S(x,y) = 1 + 1 + 1 = 3$$
	\caption{Das ausnotierte optimale lokale Alignment von x und y.}
	\label{fig:SWResult}
\end{figure}

\clearpage
%
% ---- Bibliography ----
%
\begin{thebibliography}{5}
%
\bibitem {bib:rosenberg}
R. Fleißner, A. Friedrich, J. Gillespie, G. Giribet, K. Kjer, L. McGuffin; edited by M. Rosenberg:
Sequence Alignment: 
Methods, Models, Concepts, and Strategies, 
ISBN: 9-780520-256972

\bibitem{bib:logofatu}
Doina Logofatu:
Algorithmen und Problemlösungen mit C++\\
ISBN-10: 3-8348-0126-7\\
ISBN-13: 978-3-8348-0126-5

\bibitem{bib:pdf:thierer}
Tobias Thierer:
Bioinformatik: Neue Paradigmen in der Forschung, 
\href{http://www14.informatik.tu-muenchen.de/konferenzen/Ferienakademie02/works/Thierer/Ausarbeitung.pdf}{http://www14.informatik.tu-muenchen.de/konferenzen/Ferienakademie02/works/Thierer/Ausarbeitung.pdf},
Stand November 2011


\bibitem{bib:wiki:fibonacci}
Wikipedia: Fibonacci-Folge, 
\href{http://de.wikipedia.org/wiki/Fibonacci-Folge}{http://de.wikipedia.org/wiki/Fibonacci-Folge},
Stand November 2011

\bibitem{bib:wiki:genom}
Wikipedia: Genom, 
\href{http://de.wikipedia.org/wiki/Genom}{http://de.wikipedia.org/wiki/Genom},
Stand November 2011

\end{thebibliography}

\clearpage

\begin{appendix}  
\section*{Appendix}
\section{Beilagen}
Angehängt an diese Arbeit befinden sich die Quelltexte der vorgestellten Algorithmen in GNU Octave:
\begin{enumerate}
	\item{Fibonacci.m}
	\item{NeedlemanWunsch.m}
	\item{SmithWaterman.m}
\end{enumerate}

\vfill

\section{Der Needleman-Wunsch-Algorithmus (Pseudocode)}

\begin{algorithm}[H]
	\caption{Needleman-Wunsch-Algorithmus}\label{alg:NW}
\begin{algorithmic}
	\Function{NeedlemanWunsch}{x,y,$\sigma_{positiv}$,$\sigma_{negativ}$,$\gamma$}
		\State diag $\gets$ 0x01 \Comment Bitmasken für die Bewegungsrichtungen
		\State up $\gets$ 0x02
		\State left $\gets$ 0x04

		\State
		\State $scores \gets$ Array[length(x)][length(y)] of Integer \Comment Erstelle die Matrizen
		\State $direcitons \gets$ Array[length(x)][length(y)] of Byte

		\State
		\State $scores[0][0] \gets 0$  \Comment Erstelle den Initialzustand
		\For{$i \gets 1\dots{}length(x)$}
			\State $scores[i][0] \gets i*\gamma$
			\State $directions[i][0] \gets left$
		\EndFor
		\For{$i \gets 1\dots{}length(y)$}
			\State $scores[0][i] \gets i*\gamma$
			\State $directions[0][i] \gets up$
		\EndFor
		
		\State
		\For{$j \gets 1\dots{}length(y)$} \Comment Fülle die Matrizen
			\For{$i \gets 1\dots{}length(x)$}
				\If{$x[i-1] == y[j-1]$} \Comment Diagonale Bewegung
					\State $scores[i][j] \gets scores[i-1][j-1] + \sigma_{positiv}$
				\Else
					\State $scores[i][j] \gets scores[i-1][j-1] + \sigma_{negativ}$
				\EndIf
				\State $directions[i][j] \gets diag$
				
				\State
				\State $score \gets scores[i-1][j] + \gamma$ \Comment Horizontale Bewegung
				\If{$scores[i][j] < score$}
					\State $scores[i][j] \gets score$
					\State $directions[i][j] \gets left$
				\ElsIf{$scores[i][j] == score$}
					\State $directions[i][j] \gets directions[i][j]+left$
				\EndIf

				\State
				\State $score \gets scores[i][j-1] + \gamma$ \Comment Vertikale Bewegung
				\If{$scores[i][j] < score$}
					\State $scores[i][j] \gets score$
					\State $directions[i][j] \gets up$
				\ElsIf{$scores[i][j] == score$}
					\State $directions[i][j] \gets directions[i][j]+up$
				\EndIf
			\EndFor
		\EndFor
	\algstore{alg:NW}
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[!h]
  \ContinuedFloat
  \caption{Needleman-Wunsch-Algorithmus (2. Teil)}
\begin{algorithmic}
	\algrestore{alg:NW}
		\State $i \gets length(x)$ \Comment X-Koordinate in der Matrix
		\State $j \gets length(y)$ \Comment Y-Koordinate in der Matrix
		\State $branch \gets 1$ \Comment Aktueller 'Ast'
		\State $a \gets ""$
		\State $b \gets ""$
		\State $prevI \gets$ Stack of Integer
		\State $prevJ \gets$ Stack of Integer
		\State $prevBranch \gets$ Stack of Byte
		\State $xAlignments \gets$ List of String
		\State $yAlignments \gets$ List of String

		\State
		\While{$directions[length(x)][length(y)] > 0$} 
		\State \Comment Traceback aller optmialen Alignments
			\If{$i == 0$ \textbf{and} $j == 0$} \Comment Linke obere Ecke
				\State $branch \gets 0$
				\State \textbf{add} $a$ \textbf{to} $xAlignments$
				\State \textbf{add} $b$ \textbf{to} $yAlignments$
			\EndIf

			\State
			\If{$branch == diag$}
				\State $branch << 1$ \Comment Bitshift: diag -> up -> left
				\If{$(directions[i][j]$ \& $diag) > 0$}	\Comment Diagonale Bewegung
					\State $directions[i][j] \gets directions[i][j]-diag$
					\State \textbf{push} $i$ \textbf{onto} $prevI$
					\State \textbf{push} $j$ \textbf{onto} $prevJ$
					\State \textbf{push} $branch$ \textbf{onto} $prevBranch$
					\State $i \gets i-1$
					\State $j \gets j-1$
					\State $branch \gets 1$
					\State $a \gets x[i]+a$
					\State $b \gets y[j]+b$
				\EndIf
			\ElsIf{$branch == up$}
				\State $branch << 1$
				\If{$(directions[i][j]$ \& $up) > 0$} \Comment Vertikale Bewegung
					\State $directions[i][j] \gets directions[i][j]-up$
					\State \textbf{push} $i$ \textbf{onto} $prevI$
					\State \textbf{push} $j$ \textbf{onto} $prevJ$
					\State \textbf{push} $branch$ \textbf{onto} $prevBranch$
					\State $j \gets j-1$
					\State $branch \gets 1$
					\State $a \gets "-"+a$
					\State $b \gets y[j]+b$
				\EndIf	
			\algstore{alg:NW}
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[!h]
  \ContinuedFloat
  \caption{Needleman-Wunsch-Algorithmus (3. Teil)}
\begin{algorithmic}
			\algrestore{alg:NW}
			\ElsIf{$branch == down$}
				\State $branch << 1$
				\If{$(directions[i][j]$ \& $left) > 0$} \Comment Horizontale Bewegung
					\State $directions[i][j] \gets directions[i][j]-left$
					\State \textbf{push} $i$ \textbf{onto} $prevI$
					\State \textbf{push} $j$ \textbf{onto} $prevJ$
					\State \textbf{push} $branch$ \textbf{onto} $prevBranch$
					\State $i \gets i-1$
					\State $branch \gets 1$
					\State $a \gets x[i]+a$
					\State $b \gets "-"+b$
				\EndIf
			\Else \Comment Alle Pfade zu diesem Punkt wurden besucht
				\If{$length(prevI) == 0$} \Comment Alle 'Äste' wurden besucht
					\State \textbf{break} \Comment Brich die Schleife ab
				\EndIf
				\State \textbf{pop} $i$ \textbf{from} $prevI$ \Comment Springe zurück
				\State \textbf{pop} $j$ \textbf{from} $prevJ$
				\State \textbf{pop} $branch$ \textbf{from} $prevBranch$
				\State $a \gets substring(a, 1, length(a)-1)$
				\State $b \gets substring(b, 1, length(b)-1)$
			\EndIf
		\EndWhile
		\State \textbf{return} $xAlignments, yAlignments$
	\EndFunction
\end{algorithmic}
\end{algorithm}

\section{Der Smith-Waterman-Algorithmus (Pseudocode)}

\begin{algorithm}[H]
	\caption{Smith-Waterman-Algorithmus}\label{alg:SW}
\begin{algorithmic}
	\Function{SmithWaterman}{x,y,$\sigma_{positiv}$,$\sigma_{negativ}$,$\gamma$}
		\State diag $\gets$ 0x01 \Comment Bitmasken für die Bewegungsrichtungen
		\State up $\gets$ 0x02
		\State left $\gets$ 0x04

		\State
		\State $scores \gets$ Array[length(x)][length(y)] of Integer \Comment Erstelle die Matrizen
		\State $direcitons \gets$ Array[length(x)][length(y)] of Byte
		
		\State
		\State $maxScore  \gets 0$
		\State $prevI \gets$ Stack of Integer \Comment Diese Stacks werden zum Speichern
		\State $prevJ \gets$ Stack of Integer \Comment von Positionen mit maximalem Score verwendet
		\State $prevBranch \gets$ Stack of Byte

		\State
		\State $scores[0][0] \gets 0$  \Comment Erstelle den Initialzustand
		\For{$i \gets 1\dots{}length(x)$}
			\State $scores[i][0] \gets i*\gamma$
			\State $directions[i][0] \gets left$
		\EndFor
		\For{$i \gets 1\dots{}length(y)$}
			\State $scores[0][i] \gets i*\gamma$
			\State $directions[0][i] \gets up$
		\EndFor
		
		\State
		\For{$j \gets 1\dots{}length(y)$} \Comment Fülle die Matrizen
			\For{$i \gets 1\dots{}length(x)$}
				\If{$x[i-1] == y[j-1]$} \Comment Diagonale Bewegung
					\State $scores[i][j] \gets scores[i-1][j-1] + \sigma_{positiv}$
				\Else
					\State $scores[i][j] \gets scores[i-1][j-1] + \sigma_{negativ}$
				\EndIf
				\State $directions[i][j] \gets diag$
				
				\State
				\State $score \gets scores[i-1][j] + \gamma$ \Comment Horizontale Bewegung
				\If{$scores[i][j] < score$}
					\State $scores[i][j] \gets score$
					\State $directions[i][j] \gets left$
				\ElsIf{$scores[i][j] == score$}
					\State $directions[i][j] \gets directions[i][j]+left$
				\EndIf

				\State
				\State $score \gets scores[i][j-1] + \gamma$ \Comment Vertikale Bewegung
				\If{$scores[i][j] < score$}
					\State $scores[i][j] \gets score$
					\State $directions[i][j] \gets up$
				\ElsIf{$scores[i][j] == score$}
					\State $directions[i][j] \gets directions[i][j]+up$
				\EndIf

				\If{$scores[i][j] < 0$} \Comment "Null-Regel"
					\State $scores[i][j] \gets 0$
					\State $directions[i][j] \gets 0$
				\EndIf
		\EndFor
	\algstore{alg:SW}
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[!h]
  \ContinuedFloat
  \caption{Smith-Waterman-Algorithmus (2. Teil)}
\begin{algorithmic}
	\algrestore{alg:SW}

				\If{$scores[i][j] > maxScore$} \Comment Speichern maximaler Scorewerte
					\State $maxScore \gets scores[i][j]$
					\State \textbf{empty} $prevI$
					\State \textbf{empty} $prevJ$
					\State \textbf{empty} $prevBranch$
					\State \textbf{push} $i$ \textbf{onto} $prevI$
					\State \textbf{push} $j$ \textbf{onto} $prevJ$
					\State \textbf{push} $1$ \textbf{onto} $prevBranch$
				\EndIf
			\EndFor

		\If{$maxScore == 0$} \Comment Nur leere Alignments
			\State \textbf{return} $false$
		\EndIf
		
		\State
		\State \textbf{pop} $i$ \textbf{from} $prevI$ \Comment X-Koordinate in der Matrix
		\State \textbf{pop} $j$ \textbf{from} $prevJ$ \Comment Y-Koordinate in der Matrix
		\State \textbf{pop} $branch$ \textbf{from} $prevBranch$ \Comment Aktueller 'Ast'
		\State $a \gets ""$
		\State $b \gets ""$
		\State $xAlignments \gets$ List of String
		\State $yAlignments \gets$ List of String

		\State
		\While{$directions[length(x)][length(y)] > 0$} 
		\State \Comment Traceback aller optmialen Alignments
			\If{$scores(i,j) == 0$} \Comment Linke obere Ecke
				\State $branch \gets 0$
				\State \textbf{add} $a$ \textbf{to} $xAlignments$
				\State \textbf{add} $b$ \textbf{to} $yAlignments$
			\EndIf

			\State
			\If{$branch == diag$}
				\State $branch << 1$ \Comment Bitshift: diag -> up -> left
				\If{$(directions[i][j]$ \& $diag) > 0$}	\Comment Diagonale Bewegung
					\State $directions[i][j] \gets directions[i][j]-diag$
					\State \textbf{push} $i$ \textbf{onto} $prevI$
					\State \textbf{push} $j$ \textbf{onto} $prevJ$
					\State \textbf{push} $branch$ \textbf{onto} $prevBranch$
					\State $i \gets i-1$
					\State $j \gets j-1$
					\State $branch \gets 1$
					\State $a \gets x[i]+a$
					\State $b \gets y[j]+b$
				\EndIf
			\ElsIf{$branch == up$}
				\State $branch << 1$
				\If{$(directions[i][j]$ \& $up) > 0$} \Comment Vertikale Bewegung
					\State $directions[i][j] \gets directions[i][j]-up$
					\State \textbf{push} $i$ \textbf{onto} $prevI$
					\State \textbf{push} $j$ \textbf{onto} $prevJ$
					\State \textbf{push} $branch$ \textbf{onto} $prevBranch$
					\State $j \gets j-1$
					\State $branch \gets 1$
					\State $a \gets "-"+a$
					\State $b \gets y[j]+b$
				\EndIf	
			\algstore{alg:SW}
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[!h]
  \ContinuedFloat
  \caption{Smith-Waterman-Algorithmus (3. Teil)}
\begin{algorithmic}
			\algrestore{alg:SW}
			\ElsIf{$branch == down$}
				\State $branch << 1$
				\If{$(directions[i][j]$ \& $left) > 0$} \Comment Horizontale Bewegung
					\State $directions[i][j] \gets directions[i][j]-left$
					\State \textbf{push} $i$ \textbf{onto} $prevI$
					\State \textbf{push} $j$ \textbf{onto} $prevJ$
					\State \textbf{push} $branch$ \textbf{onto} $prevBranch$
					\State $i \gets i-1$
					\State $branch \gets 1$
					\State $a \gets x[i]+a$
					\State $b \gets "-"+b$
				\EndIf
			\Else \Comment Alle Pfade zu diesem Punkt wurden besucht
				\If{$length(prevI) == 0$} \Comment Alle 'Äste' wurden besucht
					\State \textbf{break} \Comment Brich die Schleife ab
				\EndIf
				\State \textbf{pop} $i$ \textbf{from} $prevI$ \Comment Springe zurück
				\State \textbf{pop} $j$ \textbf{from} $prevJ$
				\State \textbf{pop} $branch$ \textbf{from} $prevBranch$
				\State $a \gets substring(a, 1, length(a)-1)$
				\State $b \gets substring(b, 1, length(b)-1)$
			\EndIf
		\EndWhile
		\State \textbf{return} $xAlignments, yAlignments$
	\EndFunction
\end{algorithmic}
\end{algorithm}

\end{appendix}

\end{document}
